/*
 * @lc app=leetcode.cn id=15 lang=c
 *
 * [15] 三数之和
 */

// @lc code=start

static int compare(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

static void two_sum(int *nums, int low, int high, int target, int **results, int *count)
{
    while (low < high)
    {
        int sum = nums[low] + nums[high];
        if (sum > target)
        {
            high--;
        }
        else if (sum < target)
        {
            low++;
        }
        else
        {
            results[*count] = malloc(3 * sizeof(int)); // ?
            results[*count][0] = -target;
            results[*count][1] = nums[low];
            results[*count][2] = nums[high];
            (*count)++;
            while (++low < high && nums[low] == nums[low - 1])
            {
            }
            while (--high > low && nums[high] == nums[high + 1])
            {
            }
        }
    }
}

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int **threeSum(int *nums, int numsSize, int *returnSize, int **returnColumnSizes)
{
    if (numsSize < 3)
    {
        return NULL;
    }
    qsort(nums, numsSize, sizeof(*nums), compare);

    *returnSize = 0;
    int i, capacity = 50000;
    int **results = malloc(capacity * sizeof(int *));
    for (i = 0; i < numsSize - 2; i++)
    {
        if (i == 0 || i > 0 && nums[i] != nums[i - 1])
        {
            two_sum(nums, i + 1, numsSize - 1, -nums[i], results, returnSize);
        }
    }

    // 刷新returnColumnSizes
    *returnColumnSizes = malloc(*returnSize * sizeof(int *));
    for (i = 0; i < *returnSize; i++)
    {
        (*returnColumnSizes)[i] = 3;
    }
    return results;
}
// @lc code=end
